import math

def jump_search(array, x):
    if x < array[0] or x > array[len(array) - 1]:
        return -1
    
    best_step = int(math.sqrt(len(array)))
    prev = 0
    current_index = best_step
    n = len(array)
    while array[min(current_index, n) - 1] < x:
        prev = current_index
        current_index += best_step
        if current_index >= n:
            break
    for index in range(prev, min(current_index, n)):
        if array[index] == x:
            return index
        if array[index] > x:
            break
    return -1

def test_jump_search():
    array = [1, 2, 3, 5, 7, 9, 10, 23, 43, 50, 100]
    assert -1 == jump_search(array, 0)
    assert 0 == jump_search(array, 1)
    assert 3 == array[jump_search(array, 3)]
    assert 5 == array[jump_search(array, 5)]
    assert 23 == array[jump_search(array, 23)]
    assert 43 == array[jump_search(array, 43)]
    assert len(array) - 1 == jump_search(array, 100)

